package org.xi.dsaa.collection;

/**
 * 红黑树 Red Black Tree
 *
 * @param <E> 元素类型
 */
public class RedBlackTree<E extends Comparable<E>> {

    private Node<E> root;

    public boolean isEmpty() {
        return root == null;
    }

    public boolean exists(E value) {
        Node<E> node = root;
        while (node != null) {
            int compareResult = node.item.compareTo(value);
            if (compareResult > 0) {
                node = node.left;
            } else if (compareResult < 0) {
                node = node.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public void add(E item) {
        if (root == null) {
        }
    }

    public void addAll(E... items) {
        for (E item : items) {
            add(item);
        }
    }

    public void addAll(Iterable<E> items) {
        for (E item : items) {
            add(item);
        }
    }

    public boolean remove(E item) {
        return false;
    }

    public void printTree() {
        printTree(root);
    }

    private Node<E> x, p, gp, ggp;

    private void handleReorient(E item, Node<E> node) {
        x.black = true;
        x.left.black = true;
        x.right.black = true;

        if (!p.black) {
            gp.black = false;
            if (item.compareTo(gp.item) != item.compareTo(p.item)) {
                rotate(item, ggp);
            }
            x.black = true;
        }
        node.right.black = true;
    }

    private Node<E> add(E item, Node<E> node) {
        x = p = gp = node;

        while (x.item != item) {
            ggp = gp;
            gp = p;
            p = x;
            x = item.compareTo(x.item) < 0 ? x.left : x.right;
            if (isRedNode(x.left) && isRedNode(x.right)) {
                handleReorient(item, node);
            }
        }
        if (x != null) {
            return node;
        }

        x = new Node<>(item);
        if (item .compareTo(p.item) < 0) {
            p.left = x;
        } else {
            p.right = x;
        }
        handleReorient(item, node);
        return node;
    }

    private void printTree(Node<E> node) {
        if (node.left != null) {
            printTree(node.left);
        }
        System.out.println(node.item);
        if (node.right != null) {
            printTree(node.right);
        }
    }

    private boolean isRedNode(Node<E> node) {
        return node != null && !node.black;
    }

    private boolean isBlackNode(Node<E> node) {
        return node == null || node.black;
    }

    private Node<E> rotate(E item, Node<E> parent) {
        if (item.compareTo(parent.item) < 0) {
            return parent.left = item.compareTo(parent.left.item) < 0 ? singleRotateWithLeft(parent.left) : singleRotateWithRight(parent.left);
        } else {
            return parent.right = item.compareTo(parent.right.item) < 0 ? singleRotateWithLeft(parent.right) : singleRotateWithRight(parent.right);
        }
    }

    private Node<E> singleRotateWithLeft(Node<E> node) {
        Node<E> tmpNode = node.left;
        node.left = tmpNode.right;
        tmpNode.right = node;
        return tmpNode;
    }

    private Node<E> singleRotateWithRight(Node<E> node) {
        Node<E> tmpNode = node.right;
        node.right = tmpNode.left;
        tmpNode.left = node;
        return tmpNode;
    }

    public static class Node<E extends Comparable<E>> {
        private E item;
        private Node<E> parent;
        private Node<E> left;
        private Node<E> right;
        private boolean black;

        public Node(E item) {
            this(item, null);
        }

        public Node(E item, Node<E> parent) {
            this(item, parent, null, null, false);
        }

        public Node(E item, Node<E> parent, Node<E> left, Node<E> right, boolean black) {
            this.item = item;
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.black = black;
        }
    }

    public static void main(String[] args) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        tree.addAll(6, 3, 4, 1, 9, 8, 3, 6);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(6);
        tree.printTree();

        System.out.println();
        System.out.println();
        tree.remove(9);
        tree.printTree();
    }
}
